The 22nd International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHoc 2021)
Technical Sessions
Session Session-3
Queuing
Conference
10:30 AM
—
12:00 PM CST
Local
Jul 27 Tue, 9:30 PM
—
11:00 PM CDT
Job Dispatching Policies for Queueing Systems with Unknown Service Rates
Tuhinangshu Choudhury (Carnegie Mellon University, USA), Gauri Joshi (Carnegie Mellon University, USA), Weina Wang (Carnegie Mellon University, USA), Sanjay Shakkottai (University of Texas - Austin, USA)
0
In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as join-the-shortest-queue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel exploration-exploitation trade-off between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed bandit-based exploration policy.
Beyond Scaling: Calculable Error Bounds of the Power-of-Two-Choices Mean-Field Model in Heavy-Traffic
Hairi (Arizona State University, USA), Xin Liu (University of Michigan, USA), Lei Ying (University of Michigan, USA)
0
This paper provides a recipe for deriving calculable approximation errors of mean-field models in heavy-traffic with the focus on the well-known load balancing algorithm --- power-of-two-choices (Po2). The recipe combines Stein's method for linearized mean-field models and State Space Concentration (SSC) based on geometric tail bounds. In particular, we divide the state space into two regions, a neighborhood near the mean-field equilibrium and the complement of that. We first use a tail bound to show that the steady-state probability being outside the neighborhood is small. Then, we use a linearized mean-field model and Stein's method to characterize the generator difference, which provides the dominant term of the approximation error. From the dominant term, we are able to obtain an asymptotically-tight bound and a nonasymptotic upper bound, both are calculable bounds, not order-wise scaling results like most results in the literature. Finally, we compared the theoretical bounds with numerical evaluations to show the effectiveness of our results. We note that the simulation results show that both bounds are valid even for small size systems such as a system with only ten servers.
User Distributions in Shard-based Blockchain Network: Queueing Modeling, Game Analysis, and Protocol Design
Canhui Chen (Sun Yat-sen University, China), Qian Ma (Sun Yat-sen University, China), Xu Chen (Sun Yat-sen University, China), Jianwei Huang (The Chinese University of Hong Kong, Shenzhen, China)
0
Sharding is one of the most promising and practical methods to achieve horizontal scalability of blockchain networks. However, the increasing number of cross-shard transactions in blockchain sharding protocols may degrade the system throughput. In this paper, we investigate how to distribute users properly in the shard-based blockchains to boost the system transaction performance. We first build an open Jackson queueing network model to capture users' transaction dynamics on shards, and cast users' interactions as a shard-based blockchain game wherein each user aims to minimize its transaction confirmation time and transaction fee. We investigate the equilibrium of the game, and design a polynomial-time algorithm to find efficient equilibria with good system performance. We further design a novel sharding protocol with dynamic user distribution for the permissionless blockchain, which can maintain good performance in the long-term dynamic environment. Extensive numerical results using realistic blockchain transaction data corroborate that the proposed algorithm and designed protocol can achieve superior performance for shard-based blockchains.
Session Chair
Peshal Nayak (Samsung)
Session Session-4
Privacy and Security
Conference
1:30 PM
—
3:00 PM CST
Local
Jul 28 Wed, 12:30 AM
—
2:00 AM CDT
MultiAuth: Enable Multi-User Authentication with Single Commodity WiFi Device
Hao Kong (Shanghai Jiao Tong University, China), Li Lu (Zhejiang University, China), Jiadi Yu (Shanghai Jiao Tong University, China), Yingying Chen (Rutgers University, USA), Xiangyu Xu (Shanghai Jiao Tong University, China), Feilong Tang (Shanghai Jiao Tong University, China), Yi-Chao Chen (Shanghai Jiao Tong University, China)
0
With the increasing integration of humans and the cyber world, user authentication becomes critical to support various emerging application scenarios requiring security guarantees. Existing works utilize Channel State Information (CSI) of WiFi signals to capture single human activities for non-intrusive and device-free user authentication, but multi-user authentication remains a challenging task. In this paper, we present a multi-user authentication system, $MultiAuth$ which can authenticate multiple users with a single commodity WiFi device. The key idea is to profile multipath components of WiFi signals induced by multiple users, and construct individual CSI from the multipath components to solely characterize each user for user authentication. Specifically, we propose a MUltipath Time-of-Arrival measurement algorithm (MUTA) to profile multipath components of WiFi signals in high resolution. Then, after aggregating and separating the multipath components related to users, $MultiAuth$ constructs individual CSI based on the multipath components to solely characterize each user. To identify users, $MultiAuth$ further extracts user behavior profiles based on the individual CSI of each user through time-frequency analysis, and leverages a dual-task neural network for robust user authentication. Extensive experiments involving 3 simultaneously present users demonstrate that $MultiAuth$ is accurate and reliable for multi-user authentication with 87.6% average accuracy and 8.8% average false accept rate.
Man-in-the-Middle Attack Resistant Secret Key Generation via Channel Randomization
Yanjun Pan (University of Arizona, USA), Ziqi Xu (University of Arizona, USA), Ming Li (University of Arizona, USA), Loukas Lazos (University of Arizona, USA)
0
Physical-layer based key generation schemes exploit the channel reciprocity for secret key extraction, which can achieve information-theoretic secrecy against eavesdroppers. Such methods, although practical, have been shown to be vulnerable against man-in-the-middle (MitM) attacks, where an active adversary, Mallory, can influence and infer part of the secret key generated between Alice and Bob by injecting her own packet upon observing highly correlated channel/RSS measurements from Alice and Bob. As all the channels remain stable within the channel coherence time, Mallory's injected packets cause Alice and Bob to measure similar RSS, which allows Mallory to successfully predict the derived key bits. To defend against such a MitM attack, we propose to utilize a reconfigurable antenna at one of the legitimate transceivers to proactively randomize the channel state across different channel probing rounds. The randomization of the antenna mode at every probing round breaks the temporal correlation of the channels from the adversary to the legitimate devices, while preserving the reciprocity of the channel between the latter. This prevents key injection from the adversary without affecting Alice and Bob's ability to measure common randomness. We theoretically analyze the security of the protocol and conduct extensive simulations and real-world experiments to evaluate its performance. Our results show that our approach eliminates the advantage of an active MitM attack by driving down the probability of successfully guessing bits of the secret key to a random guess.
DeepLoRa: Fingerprinting LoRa Devices at Scale Through Deep Learning and Data Augmentation
Amani Al-Shawabka (Northeastern University, USA), Philip Pietraski (InterDigital Communications, USA), Sudhir B Pattar (InterDigital Communications, USA), Francesco Restuccia (Northeastern University, USA), Tommaso Melodia (Northeastern University, USA)
0
The Long Range (LoRa) protocol for low-power wide-area networks(LPWANs) is a strong candidate to enable the massive roll-out of the Internet of Things (IoT) because of its low cost, impressive sensitivity (better than -137dBm), and massive scalability potential. As tens of thousands of tiny LoRa devices are deployed over large geographic areas, a key component to the success of LoRa will be the development of reliable and robust authentication mechanisms. To this end, Radio Frequency Fingerprinting (RFFP) through deep learning (DL) has been heralded as an effective zero-power supplement or alternative to energy-hungry cryptography. Existing work on LoRa RFFP has mostly focused on small-scale testbeds and low-dimensional learning techniques; however, many challenges remain. Key among them are authentication techniques robust to a wide variety of channel variations over time and supporting a vast population of devices. In this work, we advance the state of the art by presenting (I) the first massive experimental evaluation of DL RFFP and (ii) new data augmentation techniques for LoRa designed to counter the degradation introduced by the wireless channel. Specifically, we collected and publicly shared more than 1TB of waveform data from 100 bit-similar devices (with identical manufacturing processes) over different deployment scenarios (outdoor vs. indoor) and spanning several days. We train and test diverse DL models (convolutional and recurrent neural networks) using either preamble or payload data slices. We compare three different representations of the received signal: (i)IQ, (ii) amplitude-phase, and (iii) spectrogram. Finally, we propose a novel data augmentation technique called DeepLoRa to enhance LoRa RFFP performance. Results show that (i) training the CNN models with IQ representation is not always the best combo in fingerprinting LoRa radios; training CNNs and RNN-LSTMs with amplitude-phase and spectrogram representations may increase the fingerprinting performance in small and medium-scale testbeds;(ii) using only payload data in the fingerprinting process outperforms preamble only data, and (iii)DeepLoRadata augmentation technique improves the classification accuracy from 19% to 36% intheRFFP challenging case of training on data collected on a different day than the testing data. Moreover, DeepLoRa raises the RFFP accuracy from 82% to 91% when training and testing 100 devices with data collected on the same day.
Session Chair
Meng Jin (SJTU)
Session Session-5
Age-of-Information
Conference
3:30 PM
—
5:30 PM CST
Local
Jul 28 Wed, 2:30 AM
—
4:30 AM CDT
Minimizing Age-of-Information in Heterogeneous Multi-Channel Systems: A New Partial-Index Approach
Yihan Zou (Purdue University, USA), Kwang Taik Kim (Purdue University, USA), Xiaojun Lin (Purdue University, USA), Mung Chiang (Purdue University, USA)
0
We study how to schedule data sources in a wireless time-sensitive information system with multiple heterogeneous and unreliable channels to minimize the total expected Age-of-Information (AoI). Although one could formulate this problem as a discrete-time Markov Decision Process (MDP), such an approach suffers from the curse of dimensionality and lack of insights. For single-channel systems, prior studies have developed lower-complexity solutions based on the Whittle index. However, Whittle index has not been studied for systems with multiple heterogeneous channels, mainly because indexability is not well defined when there are multiple dual cost values, one for each channel. To overcome this difficulty, we introduce new notions of partial indexability and partial index, which are defined with respect to one channel's cost, given the all other channels' costs. We then combine the ideas of partial indices and max-weight matching to develop a Sum Weighted Index Matching (SWIM) policy, which iteratively updates the dual costs and partial indices. The proposed policy is shown to be asymptotically optimal in minimizing the total expected AoI, under a technical condition on a global attractor property. Extensive performance simulations demonstrate that the proposed policy offers significant gains over conventional approaches by achieving a near-optimal AoI. Further, the notion of partial index is of independent interest and could be useful for other problems with multiple heterogeneous resources.
Minimizing Age of Information via Scheduling over Heterogeneous Channels
Jiayu Pan (The Ohio State University, USA), Ahmed M. Bedewy (The Ohio State University, USA), Yin Sun (Auburn University, USA), Ness B. Shroff (The Ohio State University, USA)
0
In this paper, we study the problem of minimizing the age of information when a source can transmit status updates over two heterogeneous channels. Our work is motivated by recent developments in 5G mmWave technology, where transmissions may occur over an unreliable but fast (e.g., mmWave) channel or a slow reliable (e.g., sub-6GHz) channel. The unreliable channel is modeled as a time-correlated Gilbert-Elliot channel, where information can be transmitted at a high rate when the channel is in the ��ON�� state. The reliable channel provides a deterministic but lower data rate. The scheduling strategy determines the channel to be used for transmission with the aim to minimize the time-average age of information (AoI). The optimal scheduling problem is formulated as a Markov Decision Process (MDP), which in our setting poses some significant challenges because e.g., supermodularity does not hold for part of the state space. We show that there exists a multi-dimensional threshold-based scheduling policy that is optimal for minimizing the age. A low-complexity bisection algorithm is further devised to compute the optimal thresholds. Numerical simulations are provided to compare different scheduling policies.
Battle between Rate and Error in Minimizing Age of Information
Guidan Yao (The Ohio State University, USA), Ahmed M. Bedewy (The Ohio State University, USA), Ness B. Shroff (The Ohio State University, USA)
0
In this paper, we consider a status update system, in which update packets are sent to the destination via a wireless medium that allows for multiple rates, where a higher rate also naturally corresponds to a higher error probability. The data freshness is measured using age of information, which is defined as the age of the recent update at the destination. A packet that is transmitted with a higher rate, will encounter a shorter delay and a higher error probability. Thus, the choice of the transmission rate affects the age at the destination. In this paper, we design a low-complexity scheduler that selects between two different transmission rate and error probability pairs to be used at each transmission epoch. This problem can be cast as a Markov Decision Process. We show that there exists a threshold-type policy that is age-optimal. More importantly, we show that the objective function is quasi-convex or non-decreasing in the threshold, based on the system parameters values. This enables us to devise a \emph{low-complexity algorithm} to minimize the age. These results reveal an interesting phenomenon: While choosing the rate with minimum mean delay is delay-optimal, this does not necessarily minimize the age.
An Online Learning Approach to Optimizing Time-Varying Costs of AoI
Vishrant Tripathi (Massachusetts Institute of Technology, USA), Eytan Modiano (Massachusetts Institute of Technology, USA)
0
We consider systems that require timely monitoring of sources over a communication network, where the cost of delayed information is unknown, time-varying and possibly adversarial. For the single source monitoring problem, we design algorithms that achieve sublinear regret compared to the best fixed policy in hindsight. For the multiple source scheduling problem, we design a new online learning algorithm called *Follow the Perturbed Whittle Leader* and show that it has low regret compared to the best fixed scheduling policy in hindsight, while remaining computationally feasible. The algorithm and its regret analysis are novel and of independent interest to the study of online restless multi-armed bandit problems. We further design algorithms that achieve sublinear regret compared to the best dynamic policy when the environment is slowly varying. Finally, we apply our algorithms to a mobility tracking problem. We consider non-stationary and adversarial mobility models and illustrate the performance benefit of using our online learning algorithms compared to an oblivious scheduling policy.
Session Chair
Xiaoying Liu (Zhejiang University of Technology)
Made with in Toronto · Privacy Policy · MobiHoc 2020 · © 2021 Duetone Corp.